package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.TreeProblem;

/**
 * 骚气方法多的是.
 * 1. 使用前序中序还原树的思路.
 * 2. 使用LeetCode本身的序列化为数组的思路.
 * 3. JSON encode和decode, 不过要引入外部库.
 * 4. 层次遍历, 加入很多null.
 * 5. 括号嵌套
 * 6. 网络协议或者HFile这种的序列化, 就是固定长度格式的, 或者把长度写进数据里的.
 * <p>
 * 长度法
 * <p>
 * <p>
 *
 * @author tzp
 * @since 2020/10/13
 */
public class LC297_2 implements TreeProblem {
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if (root == null) return "";
        String sLeft = serialize(root.left);
        String sRight = serialize(root.right);
        return root.val + "," + sLeft.length() + "," + sRight.length() + ","
                + sLeft + sRight;
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if (data == null || data.length() == 0) return null;
        return deserialize(data, 0, data.length() - 1);
    }

    public TreeNode deserialize(String data, int start, int end) {//both include.
        int comma0Index = data.indexOf(',', start);
        int comma1Index = data.indexOf(',', comma0Index + 1);
        int comma2Index = data.indexOf(',', comma1Index + 1);
        TreeNode cur = new TreeNode(Integer.parseInt(data.substring(start, comma0Index)));
        int lengthLeft = Integer.parseInt(data.substring(comma0Index + 1, comma1Index));
        int lengthRight = Integer.parseInt(data.substring(comma1Index + 1, comma2Index));
        if (lengthLeft > 0) {
            cur.left = deserialize(data, comma2Index + 1, comma2Index + 1 + lengthLeft);
        }
        if (lengthRight > 0) {
            cur.right = deserialize(data, comma2Index + 1 + lengthLeft, end);
        }
        return cur;
    }

    public static void main(String[] args) {
//        Integer[] a = {1, 2, 4, 3, 5, 7, 10, 6, null, 8, null, 11, 9, 15, null, null, null, 12, null, null, null, 13, null, null, null, null, 14};
        Integer[] a = {4, -7, -3, null, null, -9, -3, 9, -7, -4, null, 6, null, -6, -6, null, null, 0, 6, 5, null, 9, null, null, -1, -4, null, null, null, -2};
        TreeNode treeNode = TreeNode.arrayToTreeNode(a);
        String xx = new LC297_2().serialize(treeNode);
        System.out.println(xx);
        TreeNode oo = new LC297_2().deserialize(xx);
        System.out.println(oo);
    }
}
